package chapter03;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class ZigzagLevelOrder103 {
    /**
     * 利用双端队列层序遍历
     * process(dq,direct) 处理dq中节点 dq中节点在同一层 direct为true从左到右层序遍历 反之
     * 规定 无论是从左到右层序遍历 还是从右到左层序遍历 双端队列中存储的每一层节点都是按照普通队列存放
     * 即双端队列存放的节点如果只从头出节点 就是普通的层序遍历
     * 首先将根节点放入双端队列 direct为true
     * 递归出口
     *  1).队列为空时 直接返回
     *     dq.isEmpty()==true
     *     return
     *  2).遍历dq 取出节点并处理该节点 根据direct不同 考虑如果将该节点左右子树加入队列work头部还是尾部
     *     将处理的结果加入res 递归work
     *     a).direct==true 和普通层序遍历相同
     *        从头部出队列 假设出队列的节点为x 处理x 如果左右子树不为空再先将x左子树再将x右子树加入队列的尾部 循环直到队列为空
     *        while !dq.isEmpty()
     *          cur=dq.remove()     双端队列remove 和 removeFirst等价
     *          path.add(cur.val)   双端队列add 和 addLast等价
     *          if cur.left!=null -> work.add(cur.left)
     *          if cur.right!=null -> work.add(cur.right)
     *        res.add(path)
     *        process(work,!direct)
     *    b).从尾部出队列 假设出队列的节点为x 处理x 如果左右子树不为空再先将x右子树再将x左子树加入队列的头部 循环直到队列为空
     *       while !dq.isEmpty()
     *          cur=dq.removeLast();
     *          path.add(cur.val);
     *          if cur.right!=null -> work.addFirst(cur.right)
     *          if cur.left!=null -> work.addFirst(cur.left)
     *       res.add(path)
     *       process(work,!direct)
     */
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }

    List<List<Integer>> res;
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        res=new LinkedList<>();
        if(root==null){
            return res;
        }
        Deque<TreeNode> dq=new ArrayDeque<>();
        dq.add(root);
        process(dq,true);
        return res;
    }

    public void process(Deque<TreeNode> dq,boolean direct){
        if(dq.isEmpty()){
            return;
        }
        Deque<TreeNode> work=new ArrayDeque<>();
        List<Integer> path=new LinkedList<>();
        if(direct){
            while(!dq.isEmpty()){
                TreeNode cur=dq.remove();
                path.add(cur.val);
                if(cur.left!=null){
                    work.add(cur.left);
                }
                if(cur.right!=null){
                    work.add(cur.right);
                }
            }
        }else{
            while(!dq.isEmpty()){
                TreeNode cur=dq.removeLast();
                path.add(cur.val);
                if(cur.right!=null){
                    work.addFirst(cur.right);
                }
                if(cur.left!=null){
                    work.addFirst(cur.left);
                }
            }
        }
        res.add(path);
        process(work,!direct);
    }
}
